from game import GameState, GameAction, TIE
import copy
import random
import heapq 

#Global Constants
WHITE = 'W'
BLACK = 'B'

DIRECTIONS = ('N', 'S', 'W', 'E')

BOARD_SIZES   =   (7,)
NUM_PIECES    =   (1,     2)
NUM_WALLS     =   (4,     8,       12)

#The length of games in the tournament is limited to this value
MAX_TURNS = 1000 

#The setup time and turn time in the tournament will be taken from this range
MIN_TIMELIMIT = 2
MAX_TIMELIMIT = 15

# numPieces  :  [position_1, ..., position_numPieces]
START_POSITIONS={ 1:[3] , 2:[2,4]}

# receives location and direction and returns the new location after moving in the specified direction                  
def GetNextLocation(loc, direction):
    if (direction == 'N'):      return (loc[0] - 1, loc[1])
    elif (direction == 'S'):    return (loc[0] + 1, loc[1])
    elif (direction == 'W'):    return (loc[0], loc[1] - 1)
    elif (direction == 'E'):    return (loc[0], loc[1] + 1)           
    return None
                  
                  
class QuoridorState(GameState):
    
    # static (class) variables
    BrdPrintMat = []    
    
    # board profile structure is
    #                             ProfileIndex : (numPiecesNdx, numWallsNdx)
    #                             ProfileIndex = 0 is reserved (for non-initial state)
    # In the assignment you are required to use only default board profile,  BOARD_PROFILES[2] (0,1)
    # In the tournament we will use several different board profiles. 
    BOARD_PROFILES ={ 0:None, \
                      2 :(0,1) }

                      
    # C'tor helper for initial state        
    def _initFirstBrd(self, brdParameters):                
        numPiecesNdx = brdParameters[0]
        NumWallsNdx = brdParameters[1]
        
        self.brdSize = BOARD_SIZES[0]
        self.curPlayer = WHITE
        self.numPieces = NUM_PIECES[numPiecesNdx]  
        self.turnsLeft = MAX_TURNS
        
        #walls-left counters        
        self.WallsLeftW = int(NUM_WALLS[NumWallsNdx])
        self.WallsLeftB = self.WallsLeftW        
        
        #wall locations
        self.wallsH = [ [ 0 for i in xrange(self.brdSize) ] for i in xrange(self.brdSize-1) ]
        self.wallsV = [ [ 0 for i in xrange(self.brdSize) ] for i in xrange(self.brdSize-1) ]
        
        #"critical" walls
        self._criticalWallsV = { player:None for player in [WHITE, BLACK] }
        self._criticalWallsH = { player:None for player in [WHITE, BLACK] }
        
        #piece locations
        self.locationsB = []
        self.locationsW = []
        startPositions = START_POSITIONS[self.numPieces]
        for pos in startPositions:
            self.locationsW.append((0, pos))
            self.locationsB.append((self.brdSize - 1, pos))
        
    # C'tor for initial state or from other state (as a copy c'tor)  
    def __init__(self, boardProfile = 0, otherState = None):
        if (boardProfile == 0):
            self.brdSize    = otherState.brdSize
            self.numPieces  = otherState.numPieces
            self.curPlayer  = otherState.curPlayer
            self.turnsLeft  = otherState.turnsLeft
            self.wallsH     = otherState.wallsH[:]
            self.wallsV     = otherState.wallsV[:]
            self.locationsB = otherState.locationsB[:]
            self.locationsW = otherState.locationsW[:]
            self.WallsLeftB = otherState.WallsLeftB
            self.WallsLeftW = otherState.WallsLeftW
            self._criticalWallsH = otherState._criticalWallsH.copy()
            self._criticalWallsV = otherState._criticalWallsV.copy()
        
        else:             
            self._initFirstBrd(QuoridorState.BOARD_PROFILES[boardProfile])
        
    # returns a dictionary of <action, successor state>
    def getSuccessors(self):
        succDic = {}
                    
        if (self.curPlayer == WHITE):
            myLocations = self.locationsW[:]
            rivalLocations = self.locationsB[:]
            nextPlayer = BLACK
        else:
            myLocations = self.locationsB[:]
            rivalLocations = self.locationsW[:]
            nextPlayer = WHITE
        
        # Move actions
        for pieceNdx in xrange(self.numPieces):
            pieceLoc = myLocations[pieceNdx]
            if pieceLoc is None: #location is None if the piece has reached the goal (then it is removed from the board) 
                continue            
            for dir in DIRECTIONS:                        
                action = QuoridorAction('M',[pieceNdx, dir])       
                nextLoc = GetNextLocation(pieceLoc, dir)
                nextRow = nextLoc[0]
                nextCol = nextLoc[1]   
                
                #moves out of board
                if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
                    continue
                #move illegal because of wall
                if not self._moveOkByWalls(dir, nextRow, nextCol):
                    continue
                
                # jump-over moves
                if (nextLoc in rivalLocations or nextLoc in myLocations): 
                    nextLoc = GetNextLocation(nextLoc, dir)         
                    nextRow = nextLoc[0]
                    nextCol = nextLoc[1]                    
                    
                    #jump-over move blocked by another piece
                    if (nextLoc in rivalLocations or nextLoc in myLocations):
                        continue
                
                    #If one of the players has "exited the board" and reached his goal, don't check for walls or boundaries
                    if (self.curPlayer == WHITE and nextRow >= self.brdSize) or (self.curPlayer == BLACK and nextRow < 0):
                        pass
                    else:
                        if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
                            continue
                        if not self._moveOkByWalls(dir, nextRow, nextCol):
                            continue
                
                if (self.curPlayer == WHITE):
                    newLocationsW = myLocations[:]
                    if (nextRow >= self.brdSize - 1):
                        nextLoc = None
                    newLocationsW[pieceNdx] = nextLoc
                    newLocationsB = rivalLocations
                    
                elif (self.curPlayer == BLACK):
                    newLocationsB = myLocations[:]
                    if (nextRow <= 0):
                        nextLoc = None
                    newLocationsB[pieceNdx] = nextLoc
                    newLocationsW = rivalLocations
                                                   
                nextState = QuoridorState(0, self)
                nextState.curPlayer = nextPlayer
                nextState.turnsLeft = self.turnsLeft - 1
                nextState.locationsB = newLocationsB
                nextState.locationsW = newLocationsW
				                
				#Update the next state's "critical walls" (also make sure that the next state is legal)
                is_legal = True
                for player in [WHITE, BLACK]:
                    is_legal = is_legal and nextState._isThereALegalWayToFinish(player)
                assert is_legal
                
                succDic[action] = nextState
        
        # Wall actions
        if (self.curPlayer == WHITE):
            if self.WallsLeftW <= 0:
                return succDic
            newWallsLeftW = self.WallsLeftW - 1
            newWallsLeftB = self.WallsLeftB
            
        elif (self.curPlayer == BLACK):
            if self.WallsLeftB <= 0:
                return succDic
            newWallsLeftW = self.WallsLeftW
            newWallsLeftB = self.WallsLeftB - 1
                
        #copies wall matrix of a certain orientation (Horizontal/Vertical)
        def _CopyWalls(walls):
            N = self.brdSize
            newWalls = [ [ walls[i][j] for j in xrange(N) ] for i in xrange(N-1) ]
            return newWalls
                
        for firstNdx in xrange(self.brdSize - 1):
            for secondNdx in xrange(self.brdSize - 1):
                
                #Handle vertical walls
                if (self.wallsV[firstNdx][secondNdx] == 0 and self.wallsV[firstNdx][secondNdx+1] == 0 and\
                    not (self.wallsH[secondNdx][firstNdx] == 1 and self.wallsH[secondNdx][firstNdx+1] == 1) ):
                    actionV = QuoridorAction('WV',[firstNdx, secondNdx])
                    
                    newWallsV = _CopyWalls(self.wallsV)
                    newWallsV[firstNdx][secondNdx] = 1
                    newWallsV[firstNdx][secondNdx+1] = 1   
                    
                    newStateV = QuoridorState(0, self)
                    newStateV.curPlayer = nextPlayer
                    newStateV.turnsLeft = self.turnsLeft - 1
                    newStateV.wallsV = newWallsV
                    newStateV.WallsLeftW = newWallsLeftW
                    newStateV.WallsLeftB = newWallsLeftB

                    #Check there is a legal way to finish for both players
                    is_legal = True
                    for player in [WHITE, BLACK]:
                        if self._criticalWallsV[player] is None or \
                            (firstNdx, secondNdx) in self._criticalWallsV[player] or \
                            (firstNdx, secondNdx+1) in self._criticalWallsV[player]:
                                is_legal = is_legal and newStateV._isThereALegalWayToFinish(player)
                                
                    if not is_legal:
                        continue
                        
                    succDic[actionV] = newStateV
                
                #Handle horizontal walls (equivalent to previous case of vertical walls)
                if (self.wallsH[firstNdx][secondNdx] == 0 and self.wallsH[firstNdx][secondNdx+1] == 0 and\
                    not (self.wallsV[secondNdx][firstNdx] == 1 and self.wallsV[secondNdx][firstNdx+1] == 1) ):
                    actionH = QuoridorAction('WH',[firstNdx, secondNdx])
                    newWallsH = _CopyWalls(self.wallsH)
                    newWallsH[firstNdx][secondNdx] = 1
                    newWallsH[firstNdx][secondNdx+1] = 1   
                    
                    newStateH = QuoridorState(0, self)
                    newStateH.curPlayer = nextPlayer
                    newStateH.turnsLeft = self.turnsLeft - 1
                    newStateH.wallsH = newWallsH  
                    newStateH.WallsLeftW = newWallsLeftW
                    newStateH.WallsLeftB = newWallsLeftB

                    #Check there is a legal way to finish for both players
                    is_legal = True
                    for player in [WHITE, BLACK]:
                        if self._criticalWallsH[player] is None or \
                            (firstNdx, secondNdx) in self._criticalWallsH[player] or \
                            (firstNdx, secondNdx+1) in self._criticalWallsH[player]:
                                is_legal = is_legal and newStateH._isThereALegalWayToFinish(player)
                                
                    if not is_legal: 
                        continue
                    
                    succDic[actionH] = newStateH
                           
        return succDic
                                
    # checks if a move is not blocked by any wall
    def _moveOkByWalls(self, dir, nextRow, nextCol):
        if (dir == 'N'):
            if self.wallsH[nextRow][nextCol] == 1:
                return False
        elif (dir == 'S'):
            if self.wallsH[nextRow-1][nextCol] == 1:
                return False
        elif (dir == 'W'):
            if self.wallsV[nextCol][nextRow] == 1:
                return False
        elif (dir == 'E'):
            if self.wallsV[nextCol-1][nextRow] == 1:
                return False
        return True
        
    # this is a helper function used for verifying a piece has a legal path to goal remaining
    def _findLegalPathPerPiece(self, player, pieceLoc):
        #Heap contains (priority, path, location) triplets
        if player == WHITE: nodeHeap = [ (self.brdSize - pieceLoc[0], [], pieceLoc) ]
        else:               nodeHeap = [ (pieceLoc[0],                [], pieceLoc) ]
        visited = set()
        
        while len(nodeHeap) > 0:
            (priority, path, loc) = heapq.heappop(nodeHeap)
            
            for direction in ['N', 'E', 'W', 'S']:
                nextLoc = GetNextLocation(loc, direction)
                nextRow = nextLoc[0]
                nextCol = nextLoc[1]
                
                if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
                    continue
                    
                if not self._moveOkByWalls(direction, nextRow, nextCol):
                    continue
                
                newPath = path[:]
                newPath.append(direction)
                
                if player == WHITE and nextRow == self.brdSize - 1:     return newPath
                elif player == BLACK and nextRow == 0:                  return newPath
                
                if loc not in visited:
                    if player == WHITE: newPriority = self.brdSize - nextLoc[0]
                    else:               newPriority = nextLoc[0]
                    heapq.heappush(nodeHeap, (newPriority, newPath, nextLoc) )
                    
            visited.add(loc)
            
        return None
        
    # this is a helper function used for verifying a player has a legal path to goal for each piece
    def _isThereALegalWayToFinish(self, player):
        if (player == WHITE):   myLocations = self.locationsW
        else:                   myLocations = self.locationsB
            
        self._criticalWallsH[player] = set()
        self._criticalWallsV[player] = set()
            
        for loc in myLocations:
            if loc is None:
			    continue
		
            path = self._findLegalPathPerPiece(player, loc)
            if path is None:
                return False
                
            nextLoc = loc
            for dir in path:
                nextLoc = GetNextLocation(nextLoc, dir)
                if dir == 'N':
                    self._criticalWallsH[player].add(nextLoc)
                elif dir == 'S':
                    wallLoc = (nextLoc[0]-1, nextLoc[1])
                    self._criticalWallsH[player].add(wallLoc)
                elif dir == 'W':
                    wallLoc = (nextLoc[1], nextLoc[0]) 
                    self._criticalWallsV[player].add(wallLoc)
                elif dir == 'E':
                    wallLoc = (nextLoc[1]-1, nextLoc[0])
                    self._criticalWallsV[player].add(wallLoc)
                
        return True
            
    def getAllPlayers(self):
        return (WHITE, BLACK)
    
    def getCurrentPlayer(self):
        return self.curPlayer
        
    def getWinner(self):
        checkB = 1
        for locB in self.locationsB:
            if locB is not None:
                checkB = 0
                break
        if checkB == 1:
            return BLACK
        
        checkW = 1
        for locW in self.locationsW:
            if locW is not None:
                checkW = 0
                break
        if checkW == 1:
            return WHITE
        
        if self.getTurnsLeft() == 0:
            return TIE
            
        return None
                    
    def getTurnsLeft(self):
        return self.turnsLeft
    
    # this is a helper function which builds an initial ASCII matrix of an empty board 
    @staticmethod
    def InitPrintBoardMat(brdSize):                 
        if QuoridorState.BrdPrintMat:
            return

        numberLine = [' ']
        for i in xrange(brdSize):
            numberLine.append('  ')
            numberLine.append(str(i % 10))
        numberLine.append('')
        
        delimLine = [' ',' ']
        for i in xrange(3*brdSize):
            delimLine.append('-')
        delimLine.append(' ')
        
        brdLine = ['|']   
        for i in xrange(3*brdSize):
            brdLine.append(' ')
        brdLine.append('|')
                        
        brdMat = [numberLine[:],delimLine[:]]
        for i in xrange(2*brdSize-1):
            if (i % 2 == 0):
                line = [str((i/2) % 10)] + brdLine[:]
            else:
                line = [' '] + brdLine[:]
            brdMat.append(line)        
        brdMat.append(delimLine[:])
        
        QuoridorState.BrdPrintMat = brdMat
        
    #(numPiecesNdx, numWallsNdx)
    @staticmethod
    def _overwriteBoardProfiles():
        QuoridorState.BOARD_PROFILES = {0:None}
        i = 1        
        for numPiecesNdx in xrange(len(NUM_PIECES)):
            for numWallsNdx in xrange(len(NUM_WALLS)):
                QuoridorState.BOARD_PROFILES[i] = (numPiecesNdx,numWallsNdx)
                i+=1
            
    def __cmp__(self, other):
        return cmp((self.wallsH, self.wallsV, self.locationsB, self.locationsW) , (other.wallsH, other.wallsV, other.locationsB, other.locationsW))
                 
    def __hash__(self):
        return hash((self.wallsH, self.wallsV, self.locationsB, self.locationsW))
    
    def __str__(self):
        QuoridorState.InitPrintBoardMat(self.brdSize)
        curBoardMat = copy.deepcopy(QuoridorState.BrdPrintMat[:])
        #print curBoardMat
        #raw_input("Press Any Key to Continue...\n") #TODO : REMOVE
        
        pieceId = 0
        for whiteLocation in self.locationsW:
            if whiteLocation is not None:
                curBoardMat [2 + 2 * whiteLocation[0]] [3 + 3 * whiteLocation[1]] = str(pieceId)
            pieceId += 1
            
        pieceId = 0
        for blackLocation in self.locationsB:
            if blackLocation is not None:
                curBoardMat [2 + 2 * blackLocation[0]] [3 + 3 * blackLocation[1]] = chr(ord('a')+pieceId)
            pieceId += 1
        
        prev = 0
        for rowNdx in xrange(self.brdSize - 1):
            for colNdx in xrange(self.brdSize):                 
                if self.wallsH[rowNdx][colNdx] == 1:
                    curBoardMat [3 + 2 * rowNdx] [3 + 3 * colNdx] = '-'
                    curBoardMat [3 + 2 * rowNdx] [4 + 3 * colNdx] = '-'
                    if (prev==1):
                        curBoardMat [3 + 2 * rowNdx] [3 + 3 * colNdx - 1] = '*'
                        prev = 0
                    else:                        
                        prev = 1
                else:
                    prev = 0
        
        for colNdx in xrange(self.brdSize-1):
            for rowNdx in xrange(self.brdSize):            
                if self.wallsV[colNdx][rowNdx] == 1:
                    curBoardMat [2 + 2 * rowNdx] [5 + 3 * colNdx] = '|'
                    if (prev==1):
                        curBoardMat [2 + 2 * rowNdx - 1] [5 + 3 * colNdx] = '*'
                        prev = 0
                    else:                        
                        prev = 1
                else:
                    prev = 0
        
        retStr = ''
        for row in curBoardMat:
            for char in row:
                retStr = retStr + char                
            retStr = retStr + '\n'                                                        
        
        retStr = retStr + '\nWalls left white: ' + str(self.WallsLeftW) + '\n'
        retStr = retStr + 'Walls left black: ' + str(self.WallsLeftB) + '\n\n'
        
        #raw_input("Press Any Key to Continue...\n") #TODO : REMOVE
        return retStr
        

class QuoridorAction(GameAction):
    '''
    Moves in one of four directions  (type = 'M', info = [ pieceIndex , 'N'\'S'\'W'\'E' ])
    or
    Places a wall  (type = 'WV' or 'WH', info = [MajorCooridnate, MinorCooridnate] )
    '''
    LegalTypes = ('M', 'WH', 'WV')
    
    def __init__(self, type, info):
        self.type = type
        self.info = info
        
    def __cmp__(self, other):
        return cmp((self.type, tuple(self.info)), (other.type, tuple(other.info)))
        
    def __hash__(self):
        return hash((self.type, tuple(self.info)))
    
    def __str__(self):
        retStr = ''
        if self.type == 'M':
            retStr += 'Move '
        if self.type == 'WH':
            retStr += 'Wall (Hor) '
        elif self.type == 'WV':
            retStr += 'Wall (Ver) '
        return retStr + str(self.info) + '\n'


def _TestShowAllBoardProfiles():
    QuoridorState._overwriteBoardProfiles()
    print QuoridorState.BOARD_PROFILES
    i = 1
    for numPiecesNdx in xrange(len(NUM_PIECES)):
        for numWallsNdx in xrange(len(NUM_WALLS)):
            state = QuoridorState(i)
            print '\nbrdSize : ' + str(BOARD_SIZES[0])
            print 'numPieces : ' + str(NUM_PIECES[numPiecesNdx])
            print 'numWalls : ' + str(NUM_WALLS[numWallsNdx]) + '\n'
            print str(state)
            raw_input("Press Any Key to Continue...\n")
            i+=1

def _TestGameSequence():
    QuoridorState._overwriteBoardProfiles()
    random.seed()
    state = QuoridorState(2)
    while 1==1:
        print state
        nextStateDictionaries = state.getSuccessors()
        moveNdx = random.randrange(len(nextStateDictionaries.keys()))
        move = nextStateDictionaries.keys()[moveNdx]
        print str(move)
        state = nextStateDictionaries[move]
        winner = state.getWinner()
        if  winner != None:
            print 'WINNER : ' + str(state.getWinner())
            break
        raw_input("Press Any Key to Continue...\n")
        
#_TestShowAllBoardProfiles()
#_TestGameSequence()
